/**
 * describe:
 *
 * @author chaP
 * @date 2019/03/24
 */
package CodingTest.AC20190324;

/**
 * 题目描述：
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返
 * 回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 */
public class deleteDuplication {
    class ListNode{
        int val;
        ListNode next = null;
        ListNode(int x){
            this.val = x;
        }
    }
    //递归法
    public ListNode deleteDuplication1(ListNode pHead){
        if(pHead == null) return null;
        if(pHead.next == null) return pHead;
        ListNode cur;
        //对重复节点的处理
        if(pHead.val == pHead.next.val){
            cur = pHead.next.next;
            //遍历到没有重复节点的位置
            while(cur != null && cur.val == pHead.val){
                cur = cur.next;
            }
            return deleteDuplication1(cur);
        }
        //该节点不重复 递归下一个节点
        cur = pHead.next;
        pHead.next = deleteDuplication1(cur);
        return pHead;

    }
    public ListNode deleteDuplication2(ListNode pHead){
        if(pHead == null &&pHead.next == null) return pHead;
        ListNode pre = null;
        pre.next = pHead;
        ListNode head = pHead;
        while(head != null && head.next != null){
            if(head.val == head.next.val){
                int val = head.val;
                while(head.next != null && val == head.next.val){
                    head = head.next;
                }
               if(pre == null){
                    pHead = head.next;
               }else{
                    pre = head;
               }
            }else{
                head = head.next;
            }

            }
            return head;
    }
}

